package edu.dayu.demo2;

import java.util.ArrayList;
import java.util.List;

/**
 * 给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能从 s 获得的 有效 IP 地址 。你可以按任何顺序返回答案。
 * 输入：s = "25525511135"
 * 输出：["255.255.11.135","255.255.111.35"]
 * 思路： 首先需要判断 ip 是否有效。 想要得到全部结果肯定需要回溯，
 *         每一位都不能超过三个数字。 可以先判断字符串的长度，必须在 4-12 的范围内。
 *         截取原字符串，用list 装 截取下来的字段，需要保证list 的大小小于等于4
 */
public class 复原IP {
    static int n;
    static List<String> ans = new ArrayList<>();
    public static void main(String[] args) {
        String s = "25525511135";
        System.out.println(restoreIpAddresses(s));
    }


    public static List<String> restoreIpAddresses(String s) {
        n = s.length();
        dfs(0, s, new ArrayList<String>());
        return ans;
    }

    public static void dfs(int start, String s, ArrayList<String> list){
        int len = list.size();
        if(len > 4) return;
        if(start == n && len == 4){
            // 拼接list中的所有字符串
            String temp = "";
            for(String str : list){
                temp += str+".";
            }
            ans.add(temp.substring(0,temp.length()-1));
            return ;
        }
        for(int i=start;i<n;i++){
            String temp = s.substring(start,i+1);
            int num = Integer.parseInt(temp);
            if(num > 255) return;
            if(num == 0 && temp.length() == 1) {  // 遏制前导零
                list.add(temp);
                dfs(i+1, s, list);
                list.remove(list.size()-1);
            }else {
                if(num <= 255 && temp.charAt(0) != '0'){
                    list.add(temp);
                    dfs(i+1, s, list);
                    list.remove(list.size()-1);
                }
            }
        }
    }
}
